package com.LeeCode;

/**
 * 黄金矿工
 */

public class Code1219 {
    public static void main(String[] args) {

    }

    private int maxGold = 0;
    private int m, n;
    private int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public int getMaximumGold(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }

        m = grid.length;
        n = grid[0].length;

        // 预处理：找出所有可能的起点
        // 只有度数<=2的点才可能是起点（度数是相邻非零单元格的数量）
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] > 0) {
                    dfs(grid, i, j, 0);
                }
            }
        }

        return maxGold;
    }

    private void dfs(int[][] grid, int row, int col, int currentGold) {
        // 边界检查
        if (row < 0 || row >= m || col < 0 || col >= n || grid[row][col] <= 0) {
            return;
        }

        int gold = grid[row][col];
        currentGold += gold;
        maxGold = Math.max(maxGold, currentGold);

        // 临时标记为已访问
        grid[row][col] = -gold;

        // 向四个方向探索
        for (int[] dir : directions) {
            dfs(grid, row + dir[0], col + dir[1], currentGold);
        }

        // 回溯
        grid[row][col] = gold;
    }
}
